﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace GPC_Overlay
{

    public class ParallelSort
    {
        #region Public Static Methods

        public static void QuicksortSequential(List<Polygon> arr)
        {
            QuicksortSequential(arr, 0, arr.Count - 1);
        }

        public static void QuicksortSequential(List<Polygon> arr, bool sortOnLowerBox)
        {
            QuicksortSequential(arr, 0, arr.Count - 1, sortOnLowerBox);
        }

        public static void QuicksortParallel(List<Polygon> arr, bool lowerBox)
        {
            QuicksortParallel(arr, 0, arr.Count - 1, lowerBox);
        }

        #endregion

        #region Private Static Methods

        private static void QuicksortSequential(List<Polygon> arr, int left, int right)
        {
            if (right > left)
            {
                int pivot = Partition(arr, left, right);
                QuicksortSequential(arr, left, pivot - 1);
                QuicksortSequential(arr, pivot + 1, right);
            }
        }

        private static void QuicksortSequential(List<Polygon> arr, int left, int right, bool sortOnLowerBox)
        {
            if (right > left)
            {
                int pivot = 0;
                if (sortOnLowerBox)
                {
                    pivot = Partition(arr, left, right);
                }
                else
                {
                    pivot = PartitionUpper(arr, left, right);
                }
                QuicksortSequential(arr, left, pivot - 1, sortOnLowerBox);
                QuicksortSequential(arr, pivot + 1, right, sortOnLowerBox);
            }
        }


        private static void QuicksortParallel(List<Polygon> arr, int left, int right, bool sortOnLowerBox)
        {
            const int SEQUENTIAL_THRESHOLD = 2048;
            if (right > left)
            {
                if (right - left < SEQUENTIAL_THRESHOLD)
                {
                    QuicksortSequential(arr, left, right);
                }
                else
                {
                    int pivot = 0;
                    if (sortOnLowerBox)
                    {
                        pivot = Partition(arr, left, right);
                    }
                    else
                    {
                        pivot = PartitionUpper(arr, left, right);
                    }

                    Parallel.Invoke
                    (new Action[] 
                    
                    {
                        delegate 
                        {
                            QuicksortParallel(arr, left, pivot - 1, sortOnLowerBox);
                        },  

                        delegate 
                        {
                            QuicksortParallel(arr, pivot + 1, right, sortOnLowerBox);
                        } 

                    }
                    );
                }
            }
        }

        private static void Swap(List<Polygon> arr, int i, int j)
        {
            Polygon tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        private static int Partition(List<Polygon> arr, int low, int high)
        {
            // Simple partitioning implementation 
            int pivotPos = (high + low) / 2;
            Polygon pivot = arr[pivotPos];
            Swap(arr, low, pivotPos);

            int left = low;
            for (int i = low + 1; i <= high; i++)
            {
                //if (arr[i].CompareTo(pivot) < 0) <- This is the original line
                if (arr[i].lowerBBox.X < pivot.lowerBBox.X)
                {
                    left++;
                    Swap(arr, i, left);
                }
            }

            Swap(arr, low, left);
            return left;
        }

        private static int PartitionUpper(List<Polygon> arr, int low, int high)
        {
            // Simple partitioning implementation 
            int pivotPos = (high + low) / 2;
            Polygon pivot = arr[pivotPos];
            Swap(arr, low, pivotPos);

            int left = low;
            for (int i = low + 1; i <= high; i++)
            {
                //if (arr[i].CompareTo(pivot) < 0) <- This is the original line
                if (arr[i].upperBBox.X < pivot.upperBBox.X)
                {
                    left++;
                    Swap(arr, i, left);
                }
            }

            Swap(arr, low, left);
            return left;
        }
        #endregion
    }


}
